package com.nl.sort;

public class FindMaxSumOfSubArray {

	
	public static int maxSum(int[] arr){
		int currentMax = 0;
		int max =0;
		int start = 0;
		int end =0;
		
		for( int i=0;i<arr.length;i++){
			if(currentMax<=0){
				currentMax = arr[i];
				start = i;
			}else{
				currentMax+=arr[i];
			}
			
			if(currentMax>max){
				max = currentMax;
				end = i;
			}
		}
		
		System.out.println(start+" - " +end);
		for(int i=start;i<=end;i++){
			System.out.print(arr[i] + " ");
		}

		System.out.println();
		return max;
	}
	
	public static void main(String[] args) {
		System.out.println(maxSum(new int[]{0,-2,10,-2,8,9,2,-3}));
	}
}
